import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;

class MyArrayList1<E>  {
    private Object[] elementData;
    private int size;

    private static  final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private static  final Object[] EMPTY_ELEMENTDATA = {};

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public MyArrayList1() {// 不带参的
        this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 带参的
    public MyArrayList1(int initialCapacity) {
        if(initialCapacity > 0){
            this.elementData = new Object[initialCapacity];
        }else if (initialCapacity == 0){
            this.elementData = EMPTY_ELEMENTDATA; // this.elementData = new Object[0];
        }else {// 初始化容量为负数，数组的大小是不可能为负数的
            // 抛出一个 非法参数异常，打印 非法参数异常 信息 ： 非法容量： 非法容量值
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }


    // 添加元素
    public boolean add(E e){
        // 1.确定 真正的容量大小
        // 2.存储之前，确认数组是否放得下 add元素。
        // 3.如果放不下，就扩容
        ensureCapacityInternal(size + 1);

        elementData[size] = e;
        size++;
        return true;
    }

    private  void ensureCapacityInternal(int minCapacity){
        // 计算 存储 add元素之后的 容量
        int capacity = calculateCapacity(elementData,minCapacity);

        //确保明确的容量
        ensureExplicitCapacity(capacity);
    }

    private int calculateCapacity(Object[] elementData,int minCapacity){
        // 1. elementData 数组 是否之前 分配过大小
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            return Math.max(10,minCapacity);
        }
        //分配过，就返回 minCapacity/size+1
        return minCapacity;
    }

    private void ensureExplicitCapacity( int minCapacity){
        // 确认数组是否放得下 add元素，如果放不下，就扩容
        // 当然前提是满足if语句的条件
        // 如果不满足，则不用扩容
        if (minCapacity -elementData.length>0){
            grow(minCapacity);// 调用扩容方法
        }
    }

    //扩容
    private void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        if (newCapacity - minCapacity<0){
            newCapacity = minCapacity;
        }
        if (newCapacity - MAX_ARRAY_SIZE>0){
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData,newCapacity);
    }
    private static int hugeCapacity(int minCapacity){
        if (minCapacity<0){
            throw  new OutOfMemoryError();
        }
        return (minCapacity>MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    public void add(int index,E e){
        rangeCheckForAdd(index);
        ensureCapacityInternal(size+1);

        // System.arraycopy 是新建一个数组 ， 将 index 前面的数据原样拷贝下来
        // 然后从 index 位置开始，将 index 位置上的元素 拷贝到 新建数组 对应的index +1 的位置。
        // 从而空出 index 位置方便插入新元素
//        System.arraycopy(elementData,index,elementData,index+1,size - index);

        // 自己写 copy
        copy(index);
        elementData[index] = e;
        size++;
    }
    private  void rangeCheckForAdd(int index){
        // index 等于0，相当于头插，等于ALsize 相当于尾插
        if (index>ALsize() || index<0){
            throw new IndexOutOfBoundsException("index 位置不合法，不能插入数据");
        }
    }
    // 获取顺序表的 大小
    public int ALsize(){
        return size;
    }

    private void copy(int index){
        for (int i = size-1; i >= index; i--) {
            elementData[i+1] = elementData[i];
        }
    }
// 删除第一次出现的指定元素
    public boolean remove(Object o){
        if (o == null){
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null){
                    fastRmeove(i);
                    return true;
                }
            }
        }else {// 非null
            for (int i = 0; i < size; i++) {
                if (o.equals(elementData[i])){
                    fastRmeove(i);// 删除第一次出现的指定元素
                    return true;
                }
            }
        }
        return false;
    }

    private void  fastRmeove (int index){
        // 计算移动元素的个数
        // size - index，只移动index之后的元素
        // 减一是为了防止越界
        int numMoved = size - index -1;

        if (numMoved>0){
            copy1(index);// 数组整体左移，覆盖index下标的元素，间接删除
        }
        elementData[--size] = null;// 将最后一个元素置为null，没用了就别留着
        //            size--;//有效元素个数减一
    }
    private void copy1(int index){
        for (int i = index; i < size; i++) {
            elementData[index] = elementData[index+1];
        }
    }

    // 删除指定位置的元素
    public Object remove(int index){
        rangeCheck(index);

        Object oldValue = elementData[index];
        int numMoved = size - index -1;
        if (numMoved>0){
            copy1(index);
        }
        elementData[--size] = null;
        return  oldValue;
    }

    private void rangeCheck(int index){
        if (index>=size){
            throw new IndexOutOfBoundsException("你输入的删除元素下标不合法，越界了");
        }
    }

    public  Object get (int index){
        rangeCheck(index);
        return elementData[index];
    }

    public Object set(int index,Object element){
        rangeCheck(index);
        Object oldValue = elementData[index];
        elementData[index] = element;
        return  oldValue;
    }

    public void clear(){
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size=0;
    }

    public boolean contains(Object o){
        return indexOf(o)>0;
    }
    public int indexOf(Object o){
        if (o == null){
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null){
                    return  i;
                }
            }
        }else{
            for (int i = 0; i < size; i++) {
                if (o.equals(elementData[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    @Override
    public String toString() {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < size-1; i++) {
                sb.append(elementData[i]);
                sb.append(",");
                sb.append(" ");
            }
        sb.append(elementData[size-1]);
        sb.append("]");
        return sb.toString();
    }

}




public class TestDemo3 {
    public static void main(String[] args) {
        MyArrayList1<String> myArrayList = new MyArrayList1<>();
        System.out.println(myArrayList);
        System.out.println("============");
        myArrayList.add("1");
        myArrayList.add("2");
        myArrayList.add("3");
        myArrayList.add("4");
        System.out.println(myArrayList);
        System.out.println("==============");
        boolean b = myArrayList.remove("4");
        System.out.println(b);
        System.out.println(myArrayList);
        System.out.println("==============");
        Object o = myArrayList.remove(1);
        System.out.println(o);
        System.out.println(myArrayList);
    }
}
